/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年10月01日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int size = nums.size();
        int result = 0;

        for(int i = 0; i < size; i++){
            result = nums[i] ^ result;
        }

        return result;
    }
};

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int size = nums.size();
        int start = 0, end = size - 1;
        while(start < end){
            int mid = (end-start)/2+start;
            if(mid % 2 == 1){
                mid--;
            }
            if(nums[mid] == nums[mid + 1]){
                start = mid+2;
            }else{
                end = mid;
            }
        }

        return nums[start];
    }
};